package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class Q153ii {
	/**
	 * @param num:    Given the candidate numbers
	 * @param target: Given the target number
	 * @return: All the combinations that sum to target
	 */
	public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		if (num == null || num.length == 0)
			return res;
		ArrayList<Integer> item = new ArrayList<Integer>();
		Arrays.sort(num);
		boolean[] visited = new boolean[num.length];
		helper(num, target, 0, item, res, visited);
		return res;
	}

	private void helper(int[] num, int target, int start, ArrayList<Integer> item, ArrayList<ArrayList<Integer>> res,
			boolean[] visited) {
		if (target < 0)
			return;
		if (target == 0) {
			res.add(new ArrayList<Integer>(item));
			return;
		}
		for (int i = start; i < num.length; i++) {
			if (!visited[i]) {
				if (i > 0 && num[i] == num[i - 1] && visited[i - 1] == false)
					continue;
				item.add(num[i]);
				visited[i] = true;
				int newtarget = target - num[i];
				helper(num, newtarget, i + 1, item, res, visited);
				visited[i] = false;
				item.remove(item.size() - 1);
			}
		}
	}
	@Test
	public void tst() {
		int num[] = { 7, 1, 2, 5, 1, 6,6, 10 };
		int target = 8;
		System.out.println(combinationSum2(num, target));
	}
}
